home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / Tool Chest / Development Tools & Languages / • Other Platforms / PCCTS / antlr / pred.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-14  |  10.5 KB  |  464 lines  |  [TEXT/MPS ]
  1. /*
  2.  * pred.c -- source for predicate detection, manipulation
  3.  *
  4.  * $Id: pred.c,v 1.7 1994/08/29 20:16:14 parrt Exp parrt $
  5.  * $Revision: 1.7 $
  6.  *
  7.  * SOFTWARE RIGHTS
  8.  *
  9.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  10.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  11.  * company may do whatever they wish with source code distributed with
  12.  * PCCTS or the code generated by PCCTS, including the incorporation of
  13.  * PCCTS, or its output, into commerical software.
  14.  * 
  15.  * We encourage users to develop software with PCCTS.  However, we do ask
  16.  * that credit is given to us for developing PCCTS.  By "credit",
  17.  * we mean that if you incorporate our source code into one of your
  18.  * programs (commercial product, research project, or otherwise) that you
  19.  * acknowledge this fact somewhere in the documentation, research report,
  20.  * etc...  If you like PCCTS and have developed a nice tool with the
  21.  * output, please mention that you developed it using PCCTS.  In
  22.  * addition, we ask that this header remain intact in our source code.
  23.  * As long as these guidelines are kept, we expect to continue enhancing
  24.  * this system and expect to make other tools available as they are
  25.  * completed.
  26.  *
  27.  * ANTLR 1.23
  28.  * Terence Parr
  29.  * Parr Research Corporation
  30.  * with Purdue University and AHPCRC, University of Minnesota
  31.  * 1989-1994
  32.  */
  33. #include <stdio.h>
  34. #ifdef __cplusplus
  35. #ifndef __STDC__
  36. #define __STDC__
  37. #endif
  38. #endif
  39. #include "set.h"
  40. #include "syn.h"
  41. #include "hash.h"
  42. #include "generic.h"
  43. #include "dlgdef.h"
  44.  
  45. #ifdef __STDC__
  46. static Predicate *new_pred(void);
  47. static void complete_context_sets(RuleRefNode *, Predicate *);
  48. static void complete_context_trees(RuleRefNode *, Predicate *);
  49. #else
  50. static Predicate *new_pred();
  51. static void complete_context_sets();
  52. static void complete_context_trees();
  53. #endif
  54.  
  55. static Predicate pred_empty = {NULL,NULL,NULL,NULL,{set_init,set_init},set_init};
  56.  
  57. /* Find all predicates in a block of alternatives.  DO NOT find predicates
  58.  * behind the block because that predicate could depend on things set in
  59.  * one of the nonoptional blocks
  60.  */
  61. Predicate *
  62. #ifdef __STDC__
  63. find_in_aSubBlk( Junction *alt )
  64. #else
  65. find_in_aSubBlk( alt )
  66. Junction *alt;
  67. #endif
  68. {
  69.     Predicate *a, *head=NULL, *tail;
  70.     Junction *p = alt;
  71.     int i=1;
  72.  
  73.     for (; p!=NULL; p=(Junction *)p->p2)
  74.     {
  75.         /* ignore empty alts */
  76.         if ( p->p1->ntype != nJunction ||
  77.              ((Junction *)p->p1)->jtype != EndBlk )
  78.         {
  79.             a = find_predicates(p->p1);
  80.             if ( a==NULL ) continue;
  81.             if ( head==NULL ) head = tail = a;
  82.             else {
  83.                 tail->right = a;
  84.                 tail = a;
  85.             }
  86.         }
  87.     }
  88.     return head;
  89. }
  90.  
  91. Predicate *
  92. #ifdef __STDC__
  93. find_in_aOptBlk( Junction *alt )
  94. #else
  95. find_in_aOptBlk( alt )
  96. Junction *alt;
  97. #endif
  98. {
  99.     return find_in_aSubBlk( alt );
  100. }
  101.  
  102. Predicate *
  103. #ifdef __STDC__
  104. find_in_aLoopBegin( Junction *alt )
  105. #else
  106. find_in_aLoopBegin( alt )
  107. Junction *alt;
  108. #endif
  109. {
  110.     return find_in_aSubBlk( (Junction *) alt->p1 );    /* get preds in alts */
  111. }
  112.  
  113. Predicate *
  114. #ifdef __STDC__
  115. find_in_aPlusBlk( Junction *alt )
  116. #else
  117. find_in_aPlusBlk( alt )
  118. Junction *alt;
  119. #endif
  120. {
  121.     require(alt!=NULL&&alt->p2!=NULL, "invalid aPlusBlk");
  122.     return find_in_aSubBlk( alt );
  123. }
  124.  
  125. /* Look for a predicate;
  126.  *
  127.  * Do not pass anything but Junction nodes; no Actions, Tokens, RuleRefs.
  128.  * This means that a "hoisting distance" of zero is the only distance
  129.  * allowable.  Init actions are ignored.
  130.  *
  131.  * WARNING:
  132.  *        Assumes no (..)? block after predicate for the moment.
  133.  *        Does not check to see if pred is in production that can generate
  134.  *            a sequence contained in the set of ambiguous tuples.
  135.  *
  136.  * Return the predicate found if any.
  137.  */
  138. Predicate *
  139. #ifdef __STDC__
  140. find_predicates( Node *alt )
  141. #else
  142. find_predicates( alt )
  143. Node *alt;
  144. #endif
  145. {
  146. #ifdef DBG_PRED
  147.     Junction *j;
  148.     RuleRefNode *r;
  149.     TokNode *t;
  150. #endif
  151.     Predicate *pred;
  152.  
  153.     if ( alt==NULL ) return NULL;
  154.  
  155. #ifdef DBG_PRED
  156.     switch ( alt->ntype )
  157.     {
  158.         case nJunction :
  159.             j = (Junction *) alt;
  160.             fprintf(stderr, "Junction(in %s)", j->rname);
  161.             switch ( j->jtype )
  162.             {
  163.                 case aSubBlk :
  164.                     fprintf(stderr,"aSubBlk\n");
  165.                     break;
  166.                 case aOptBlk :
  167.                     fprintf(stderr,"aOptBlk\n");
  168.                     break;
  169.                 case aLoopBegin :
  170.                     fprintf(stderr,"aLoopBeginBlk\n");
  171.                     break;
  172.                 case aLoopBlk :
  173.                     fprintf(stderr,"aLoopBlk\n");
  174.                     break;
  175.                 case aPlusBlk :
  176.                     fprintf(stderr,"aPlusBlk\n");
  177.                     break;
  178.                 case EndBlk :
  179.                     fprintf(stderr,"EndBlk\n");
  180.                     break;
  181.                 case RuleBlk :
  182.                     fprintf(stderr,"RuleBlk\n");
  183.                     break;
  184.                 case Generic :
  185.                     fprintf(stderr,"Generic\n");
  186.                     break;
  187.                 case EndRule :
  188.                     fprintf(stderr,"EndRule\n");
  189.                     break;
  190.             }
  191.             break;
  192.         case nRuleRef :
  193.             r = (RuleRefNode *) alt;
  194.             fprintf(stderr, "RuleRef(in %s)\n", r->rname);
  195.             break;
  196.         case nToken :
  197.             t = (TokNode *) alt;
  198.             fprintf(stderr, "TokenNode(in %s)%s\n", t->rname, TokenString(t->token));
  199.             break;
  200.         case nAction :
  201.             fprintf(stderr, "Action\n");
  202.             break;
  203.     }
  204. #endif
  205.  
  206.     switch ( alt->ntype )
  207.     {
  208.         case nJunction :
  209.         {
  210.             Predicate *a, *b;
  211.             Junction *p = (Junction *) alt;    
  212.  
  213.             /* lock nodes */
  214.             if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  215.                  p->jtype==aPlusBlk || p->jtype==EndRule )
  216.             {
  217.                 require(p->pred_lock!=NULL, "rJunc: lock array is NULL");
  218.                 if ( p->pred_lock[1] )
  219.                 {
  220.                     return NULL;
  221.                 }
  222.                 p->pred_lock[1] = TRUE;
  223.             }
  224.  
  225.             switch ( p->jtype )
  226.             {
  227.                 case aSubBlk :
  228.                     a = find_in_aSubBlk(p);
  229.                     return a;    /* nothing is visible past this guy */
  230.                 case aOptBlk :
  231.                     a = find_in_aOptBlk(p);
  232.                     return a;
  233.                 case aLoopBegin :
  234.                     a = find_in_aLoopBegin(p);
  235.                     return a;
  236.                 case aLoopBlk :
  237.                     a = find_in_aSubBlk(p);
  238.                     p->pred_lock[1] = FALSE;
  239.                     return a;
  240.                 case aPlusBlk :
  241.                     a = find_in_aPlusBlk(p);
  242.                     p->pred_lock[1] = FALSE;
  243.                     return a;    /* nothing is visible past this guy */
  244.                 case RuleBlk :
  245.                     a = find_predicates(p->p1);
  246.                     p->pred_lock[1] = FALSE;
  247.                     return a;
  248.                 case Generic :
  249.                     a = find_predicates(p->p1);
  250.                     b = find_predicates(p->p2);
  251.                     if ( p->pred_lock!=NULL ) p->pred_lock[1] = FALSE;
  252.                     if ( a==NULL ) return b;
  253.                     {
  254.                     Predicate *w;
  255.                     for (w=a; w->right!=NULL; w=w->right) {;}
  256.                     w->right = b;
  257.                     return a;
  258.                     }
  259.                 case EndBlk :
  260.                 case EndRule :    /* Find no predicates after a rule ref */
  261.                     return NULL;
  262.                 default:
  263.                     fatal("this cannot be printed\n");
  264.                     break;
  265.             }
  266.         }
  267.         case nAction :
  268.         {
  269.             ActionNode *p = (ActionNode *) alt;
  270.             if ( p->init_action ) return find_predicates(p->next);
  271.             if ( p->is_predicate )
  272.             {
  273.                 Tree *t;
  274. #ifdef DBG_PRED
  275.                 fprintf(stderr, "predicate: <<%s>>?\n", p->action);
  276. #endif
  277.                 pred = new_pred();
  278.                 if ( HoistPredicateContext && LL_k > 1 )
  279.                 {
  280.                     if ( first_item_is_guess_block((Junction *)p->next) )
  281.                     {
  282.                         warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
  283.                     }
  284.                     else
  285.                     {
  286.                         ConstrainSearch = 0;
  287.                         TRAV(p->next, LL_k, &(pred->completion), t);
  288.                         t = tshrink( t );
  289.                         t = tflatten( t );
  290.                         t = tleft_factor( t );
  291.                         pred->tcontext = t;
  292. #ifdef DBG_PRED
  293.                         fprintf(stderr, "LL(%d) context:", LL_k);
  294.                         preorder(t);
  295.                         fprintf(stderr, "\n");
  296. #endif
  297.                     }
  298.                 }
  299.                 else if ( HoistPredicateContext && LL_k == 1 )
  300.                 {
  301.                     pred->scontext[1] = empty;
  302.                     if ( first_item_is_guess_block((Junction *)p->next) )
  303.                     {
  304.                         warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
  305.                     }
  306.                     else
  307.                     {
  308.                         REACH((Junction *)p->next, 1, &(pred->completion), pred->scontext[1]);
  309. #ifdef DBG_PRED
  310.                         fprintf(stderr, "LL(1) context:");
  311.                         s_fprT(stderr, pred->scontext[1]);
  312.                         fprintf(stderr, "\n");
  313. #endif
  314.                     }
  315.                 }
  316.                 pred->expr = p->action;
  317.                 pred->down = find_predicates(p->next);
  318.                 return pred;
  319.             }
  320.             return NULL;
  321.         }
  322.         case nRuleRef :
  323.         {
  324.             Predicate *a;
  325.             RuleRefNode *p = (RuleRefNode *) alt;
  326.             Junction *r;
  327.             int save_halt;
  328.             RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
  329.             if ( q == NULL )
  330.             {
  331.                 warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
  332.                 return NULL;
  333.             }
  334.             r = RulePtr[q->rulenum];
  335.             if ( r->pred_lock[1] )
  336.             {
  337.                 /* infinite left-recursion; ignore 'cause LL sup 1 (k) analysis
  338.                  * must have seen it earlier.
  339.                  */
  340.                 return NULL;
  341.             }
  342.             save_halt = r->end->halt;
  343.             r->end->halt = TRUE;
  344. /*            a = find_predicates((Node *)r->p1);*/
  345.             a = find_predicates((Node *)r);
  346.             r->end->halt = save_halt;
  347.             if ( a==NULL ) return NULL;
  348.             /* attempt to compute the "local" FOLLOW just like in normal lookahead
  349.              * computation if needed
  350.              */
  351.             if ( LL_k==1 ) {complete_context_sets(p,a); return a;}
  352.             complete_context_trees(p,a); return a;
  353.         }
  354.         case nToken :
  355.             break;
  356.     }
  357.  
  358.     return NULL;
  359. }
  360.  
  361. static Predicate *
  362. #ifdef __STDC__
  363. new_pred( void )
  364. #else
  365. new_pred( )
  366. #endif
  367. {
  368.     Predicate *p = (Predicate *) malloc(sizeof(Predicate));
  369.     require(p!=NULL, "new_pred: cannot alloc predicate");
  370.     *p = pred_empty;
  371.     return p;
  372. }
  373.  
  374. static void
  375. #ifdef __STDC__
  376. complete_context_sets( RuleRefNode *p, Predicate *a )
  377. #else
  378. complete_context_sets( p, a )
  379. RuleRefNode *p;
  380. Predicate *a;
  381. #endif
  382. {
  383.     set rk2, b;
  384.     int k2;
  385.  
  386.     for (; a!=NULL; a=a->right)
  387.     {
  388.         rk2 = b = empty;
  389.         while ( !set_nil(a->completion) )
  390.         {
  391.             k2 = set_int(a->completion);
  392.             set_rm(k2, a->completion);
  393.             REACH(p->next, k2, &rk2, b);
  394.             set_orin(&(a->scontext[1]), b);
  395.             set_free(b);
  396.         }
  397.         set_orin(&(a->completion), rk2);/* remember what we couldn't do */
  398.         set_free(rk2);
  399. #ifdef DBG_PRED
  400.         fprintf(stderr, "LL(1) context after ruleref:");
  401.         s_fprT(stderr, a->scontext[1]);
  402.         fprintf(stderr, "\n");
  403. #endif
  404.         complete_context_sets(p, a->down);
  405.     }
  406. }
  407.  
  408. static void
  409. #ifdef __STDC__
  410. complete_context_trees( RuleRefNode *p, Predicate *a )
  411. #else
  412. complete_context_trees( p, a )
  413. RuleRefNode *p;
  414. Predicate *a;
  415. #endif
  416. {
  417.     set rk2;
  418.     int k2;
  419.     Tree *u;
  420.  
  421.     for (; a!=NULL; a=a->right)
  422.     {
  423.         rk2 = empty;
  424.         /* any k left to do? if so, link onto tree */
  425.         while ( !set_nil(a->completion) )
  426.         {    
  427.             k2 = set_int(a->completion);
  428.             set_rm(k2, a->completion);
  429.             u = NULL;
  430.             TRAV(p->next, k2, &rk2, u);
  431.             /* any subtrees missing k2 tokens, add u onto end */
  432.             a->tcontext = tlink(a->tcontext, u, k2);
  433.         }
  434.         set_orin(&(a->completion), rk2);/* remember what we couldn't do */
  435.         set_free(rk2);
  436. #ifdef DBG_PRED
  437.         fprintf(stderr, "LL(%d) context after ruleref:", LL_k);
  438.         preorder(a->tcontext);
  439.         fprintf(stderr, "\n");
  440. #endif
  441.         complete_context_trees(p, a->down);
  442.     }
  443. }
  444.  
  445. /* Walk a list of predicates and return the set of all tokens in scontext[1]'s */
  446. set
  447. #ifdef __STDC__
  448. covered_set( Predicate *p )
  449. #else
  450. covered_set( p )
  451. Predicate *p;
  452. #endif
  453. {
  454.     set a;
  455.  
  456.     a = empty;
  457.     for (; p!=NULL; p=p->right)
  458.     {
  459.         set_orin(&a, p->scontext[1]);
  460.         set_orin(&a, covered_set(p->down));
  461.     }
  462.     return a;
  463. }
  464.